package com.ting.test.algorithms.并查集;

import java.util.HashMap;
import java.util.Stack;

public class UnionFindByMap<V> {
    HashMap<V, Node<V>> indexMap = new HashMap();//给定元素和包装元素的关系
    HashMap<Node<V>, Node<V>> fatherMap = new HashMap();//存储集合中元素和元素的关系
    HashMap<Node<V>, Integer> sizeMap = new HashMap();//存储元素X代表的集合的大小，只存储代表元素


    /**
     * 如果getTopFather()方法的复杂度为O(1)
     * 则isSameSet()方法的复杂度为O(1)
     * @param x
     * @param y
     * @return
     */
    public boolean isSameSet(V x, V y) {
        Node nx = indexMap.get(x);
        Node ny = indexMap.get(y);
        return getTopFather(nx) == getTopFather(ny);
    }

    /**
     *      * 如果getTopFather()方法的复杂度为O(1)
     *      * 则union()方法的复杂度为O(1)
     * @param x
     * @param y
     */
    public void union(V x, V y) {
        Node nx = getTopFather(indexMap.get(x));
        Node ny = getTopFather(indexMap.get(y));
        int nxSize = sizeMap.get(nx);
        int nySize = sizeMap.get(ny);
        Boolean nxSmall = nxSize < nySize ? true : false;
        if (nxSmall) {
            fatherMap.put(nx, ny);//将nx的指针指向ny,表示将nx代表的集合挂载ny代表的集合上
            sizeMap.put(ny, nxSize + nySize);
            sizeMap.remove(nx);
        }

    }

    /**
     * 在寻找当前集合的代表元素时，将沿途查找到的元素的父节点全部设置为代表元素
     * 注意，每次只将涉及到的元素进行调整，其余元素不变
     * 如此则整个集合的高度会越来越低
     * 那么当getTopFather()方法调用十分频繁时(超过O(n)次)，getTopFather()方法的复杂度接近O(1)
     * @param nx
     * @return
     */
    private Node<V> getTopFather(Node nx) {
        Stack<Node<V>> stack = new Stack<>();
        Node<V> current = indexMap.get(nx);
        while (fatherMap.get(current).equals(current)) {
            stack.push(current);
        }
        while (!stack.isEmpty()) {
            fatherMap.put(stack.pop(), current);
        }
        return current;
    }

    class Node<V> {
        V v;

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }
    }
}
